package com.fjl.array.leetcode304;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/4/10 14:54
 */
/*
给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
 */
public class Clazz {
    // 前缀和矩阵
    private int[][] preMatrix;

    public Clazz(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        preMatrix = new int[row + 1][col + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                preMatrix[i][j] = preMatrix[i][j - 1] + preMatrix[i - 1][j] + matrix[i - 1][j - 1] - preMatrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preMatrix[row2 + 1][col2 + 1] - preMatrix[row2 + 1][col1] - preMatrix[row1][col2 + 1] + preMatrix[row1][col1];
    }
}
